import math
from collections import defaultdict,deque
import heapq
import sys
import math
import bisect
def input():return sys.stdin.readline().strip()
def solve():
n,m=map(int,input().split())
arr=list(map(int,input().split()))
query=[[] for j in range(int(n**0.5)+1)]
q=[0]*m
for j in range(m):
x,y=map(int,input().split())
query[int(x/n**(0.5))].append((x-1,y-1,j))
q=deque()
for j in query:
j.sort(key=lambda x:(x[1]))
for p in j:
q.append(p)
d=defaultdict(lambda :0)
j=0
curl,curr,x=1,0,0
res=[0]*m
while j<len(q):
l,r=q[j][0],q[j][1]
while curl<l:
d[arr[curl]]-=1
if d[arr[curl]]==arr[curl]-1:
x-=1
if d[arr[curl]]==arr[curl]:
x+=1
curl+=1
while curl>l:
curl-=1
d[arr[curl]]+=1
if d[arr[curl]]==arr[curl]+1:
x-=1
if d[arr[curl]]==arr[curl]:
x+=1
while curr<r:
curr+=1
d[arr[curr]]+=1
if d[arr[curr]]==arr[curr]+1:
x-=1
if d[arr[curr]]==arr[curr]:
x+=1
while curr>r:
d[arr[curr]]-=1
if d[arr[curr]]==arr[curr]-1:
x-=1
if d[arr[curr]]==arr[curr]:
x+=1
curr-=1
res[q[j][2]]=x
j+=1
for j in res:
print(j)
if __name__ == '__main__':
solve()
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define vi vector<int>
#define pb push_back
struct miquery{
int ind;
int f;
int s;
};
int len = 0;
bool cmp(miquery &a, miquery &b){
if(a.f / len == b.f / len)
return a.s > b.s;
return a.f / len < b.f / len;
}
int main(){
int n, q;
cin>>n>>q;
vi a(n);
for(int i=0; i<n; i++){
cin>>a[i];
}
len = ceil(sqrt(n));
vector<miquery> que;
for(int i=0; i<q; i++){
int l, r;
cin>>l>>r;
l--; r--;
que.pb({i, l, r});
}
sort(que.begin(), que.end(), cmp);
int l = 0, r = -1;
unordered_map<int, int> mp;
int ans = 0;
vector<pair<int,int>> res;
for(int i=0; i<q; i++){
int indi = que[i].ind;
int st = que[i].f;
int en = que[i].s;
while(r < en){
r++;
mp[a[r]]++;
if(mp[a[r]] == a[r]) ans++;
if(mp[a[r]] == a[r] + 1) ans--;
}
while(r > en){
mp[a[r]]--;
if(mp[a[r]] == a[r]) ans++;
if(mp[a[r]] == a[r] - 1) ans--;
r--;
}
while(l > st){
l--;
mp[a[l]]++;
if(mp[a[l]] == a[l]) ans++;
if(mp[a[l]] == a[l] + 1) ans--;
}
while(l < st){
mp[a[l]]--;
if(mp[a[l]] == a[l]) ans++;
if(mp[a[l]] == a[l] - 1) ans--;
l++;
}
res.pb({indi, ans});
}
sort(res.begin(), res.end());
for(int i=0; i<q; i++){
cout<<res[i].second<<"\n";
}
}1609C - Complex Market Analysis | 1657E - Star MST |
1143B - Nirvana | 1285A - Mezo Playing Zoma |
919B - Perfect Number | 894A - QAQ |
1551A - Polycarp and Coins | 313A - Ilya and Bank Account |
1469A - Regular Bracket Sequence | 919C - Seat Arrangements |
1634A - Reverse and Concatenate | 1619C - Wrong Addition |
1437A - Marketing Scheme | 1473B - String LCM |
1374A - Required Remainder | 1265E - Beautiful Mirrors |
1296A - Array with Odd Sum | 1385A - Three Pairwise Maximums |
911A - Nearest Minimums | 102B - Sum of Digits |
707A - Brain's Photos | 1331B - Limericks |
305B - Continued Fractions | 1165B - Polycarp Training |
1646C - Factorials and Powers of Two | 596A - Wilbur and Swimming Pool |
1462B - Last Year's Substring | 1608B - Build the Permutation |
1505A - Is it rated - 2 | 169A - Chores |